//在第 1 天，有一个人发现了一个秘密。 
//
// 给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在
//发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。 
//
// 给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10⁹ + 7 取余 后返回。 
//
// 
//
// 示例 1： 
//
// 输入：n = 6, delay = 2, forget = 4
//输出：5
//解释：
//第 1 天：假设第一个人叫 A 。（一个人知道秘密）
//第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
//第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
//第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
//第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
//第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）
// 
//
// 示例 2： 
//
// 输入：n = 4, delay = 1, forget = 3
//输出：6
//解释：
//第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
//第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
//第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
//第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）
// 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 1000 
// 1 <= delay < forget <= n 
// 
//
// Related Topics 队列 动态规划 模拟 👍 128 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ldltd
 * @date 2025-09-09 21:54:05
 * @description 2327.知道秘密的人数
 */
public class NumberOfPeopleAwareOfASecret{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 NumberOfPeopleAwareOfASecret fun=new NumberOfPeopleAwareOfASecret();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int peopleAwareOfSecret1(int n, int delay, int forget) {
		Deque<int[]> activeQueue = new ArrayDeque<>(); // [人数, 知道秘密的日期]
		int mod = (int)(1e9 + 7);
		int total = 0;

		// 第1天
		activeQueue.offer(new int[]{1, 1});
		total = 1;

		for (int day = 2; day <= n; day++) {
			int newPeople = 0;

			// 计算今天可以分享的人数（知道秘密天数 >= delay 且 < forget）
			for (int[] person : activeQueue) {
				int knowDays = day - person[1];
				if (knowDays >= delay && knowDays < forget) {
					newPeople = (newPeople + person[0]) % mod;
				}
			}

			// 添加新知道秘密的人
			if (newPeople > 0) {
				activeQueue.offer(new int[]{newPeople, day});
				total = (total + newPeople) % mod;
			}

			// 移除忘记的人（知道秘密天数 >= forget）
			while (!activeQueue.isEmpty() && (day - activeQueue.peek()[1]) >= forget) {
				total = (total - activeQueue.poll()[0] + mod) % mod;
			}
		}

		return total % mod;
	}
	// 动态规划
	public int peopleAwareOfSecret2(int n, int delay, int forget) {
		int mod = (int)(1e9 + 7);
		long[] dp = new long[n + 1]; // dp[i]表示第i天新增知道秘密的人数
		dp[1] = 1;
		long total = 1; // 当前知道秘密的总人数

		for (int day = 2; day <= n; day++) {
			// 计算今天可以分享的人数：从day-delut到day-forget-1天新增的人
			long canShare = 0;
			for (int d = Math.max(1, day - forget + 1); d <= day - delay; d++) {
				canShare = (canShare + dp[d]) % mod;
			}

			dp[day] = canShare; // 今天新增的人数
			total = (total + canShare) % mod;

			// 减去忘记的人数（forget天前新增的人）
			if (day > forget) {
				total = (total - dp[day - forget] + mod) % mod;
			}
		}

		return (int)(total % mod);
	}
	//前缀和
	public int peopleAwareOfSecret(int n, int delay, int forget) {
		int mod = (int)(1e9 + 7);
		long[] dp = new long[n + 1];
		long[] prefix = new long[n + 1];
		dp[1] = 1;
		prefix[1] = 1;

		for (int day = 2; day <= n; day++) {
			// 计算可以分享的区间：[max(1, day-forget+1), day-delay]
			int left = Math.max(1, day - forget + 1);
			int right = day - delay;

			long canShare = 0;
			if (left <= right) {
				canShare = (prefix[right] - (left > 1 ? prefix[left - 1] : 0) + mod) % mod;
			}

			dp[day] = canShare;
			prefix[day] = (prefix[day - 1] + canShare) % mod;
		}

		// 计算最后forget天内新增的人数（这些人还没忘记）
		long result = 0;
		for (int day = Math.max(1, n - forget + 1); day <= n; day++) {
			result = (result + dp[day]) % mod;
		}

		return (int)(result % mod);
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
